1. Field of the Invention
This invention relates to memory systems, and more particularly, to methods for managing memory systems, and still more particularly to a method for segregating active and stable blocks for improved memory response time.
2. Background Information
The development of storage management systems has a long history with many related branches of research. Over the years, a great deal of attention has been given to the allocation and deallocation of memory structures. Many memory structures of interest are shown by Deitel, H. M., An Introduction to Operating Systems, Addison-Wesley, Mass., Chapter 7, 1982. Other major issues are discussed by Knuth, D., The Art of Computer Programming, Vol. 1: Fundamental Algorithms, Addison-Wesley, Reading, Mass., 1968. The invention herein described is concerned primarily with computer systems having heap managed memories, and is used together with or independently from a garbage collection scheme. A "heap managed" memory is one in which the memory is allocated and freed (either explicitly or implicitly) without regard to the temporal order or the size of the memory unit under consideration. A garbage collected memory is one in which usable memory is automatically reclaimed, and the memory may be reorganized from time to time to efficiently utilize the space of the memory, as needed. A survey of garbage collection techniques and related background materials is presented by Cohen, J., "Garbage Collection of Linked Data Structures", Computing Surveys, Vol. 13, No. 3, September, 1981, pp. 341-367. P. Bishop discusses garbage collection in very large address spaces in "Garbage Collection in a Very Large Address Space", Massachusetts Institute of Technology, Working Paper 111, September 1975.
Additionally, the overall size of a virtual memory space is often of concern, since garbage collection costs increase with the size of the space being collected, not with the amount of garbage being reclaimed.
In the operation of a typical memory system and associated central processing unit (CPU), the CPU requests the allocation of memory space as needed. Often, the allocation of the memory is done in a virtual address space. As the virtual address space becomes fully allocated, eventually requests for additional space must be denied, until reusable space in the previously allocated virtual address space has been identified and reclaimed.
As used herein, the term "physical memory" means the actual physical memory, including the main memory, usually RAM semiconductor devices, and the backing store, usually a paging disk. The term "virtual address space" is used to mean a uniform, linear, and homogeneous apparent memory space.
Generally in memory systems of the type to which the invention pertains, portions of memory are allocated in "blocks" of size specified by the CPU. Each block has a header in which various pieces of information are contained pertaining to the block, including, for example, the identification of the block, its size, and other things which may be of interest. Also contained in the block header is a field containing a reference count. The reference count of a block indicates the number of references to the block from any other block, or itself. One form of reference count is shown by Deutsch et al., "An Efficient, Incremental, Automatic Garbage Collector", CACM, Vol. 19, No. 9, September, 1976, pp. 522-526. In the type of memory to which the method of this invention pertains, when a block is initially allocated, it has a reference count of zero. Any time a new reference is established, the reference count is incremented. When a reference within a block is destroyed, the reference count of the target block is decremented. Except when a block is originally created, when the reference count of a block is decremented to zero, the block is considered to be garbage, and the space it occupies can be reclaimed.
In the memory management systems in the past, as blocks were allocated and deallocated, often pages containing very few blocks were paged out to disk to make room for further block allocation. As the need arose for access to the paged out blocks, usually, some additional page in the main memory would need to be paged out to make room for the page to be brought in from the disk. Then, the sparsely populated page is brought into the main memory from the disk, and the block needed used, after which it is almost immediately written back out to the disk. It can be seen that this produces a great deal of "thrashing", involving rapid, frequent disk fetch and write operations, and is undesirable since it greatly slows down memory operations.
What is needed is a method for managing a memory in which blocks are efficiently stored in a manner by which those which are infrequently needed are collected and completely stored and paged out onto disk, and blocks which are frequently used are collected and maintained in main memory for efficient access.